Ordnung schaffen - Bäume
Binärer Suchbaum
Wenn wir ausgehend von der binären Suche in einer Liste jeweils die Elemente verbinden, die die Liste halbieren, entsteht eine neue, sehr praktische Datenstruktur - ein Baum.
Ein Baum weist mehrere Bestandteile auf:
Der Vorteil eines Baumes (in unserem Fall eines binären Suchbaumes) besteht darin, dass man die Werte, die man im Baum verwaltet, nicht sortieren muss, sondern man baut den Baum nach bestimmten Regeln auf und kann dann relativ schnell jeden Eintrag wieder finden. Ein solcher binärer Suchbaum wird nach folgendem Schema aufgebaut:
Der erste Wert kommt in die Wurzel. Der Wert des nächsten Listenelements wird mit dem in der Wurzel eingetragenen verglichen. Ist er kleiner, wird ein 'linkes Kind' erzeugt und der Wert dort abgelegt. Andernfalls erzeugen wir ein 'rechtes Kind', in dem wir unseren Wert ablegen. Ist der Knoten, in den man eintragen will schon belegt, vergleicht man ihn mit dem einzutragenden Wert auf die bereits beschriebene Weise und steigt somit den Baum solange herunter, bis der eigentliche Eintrag erfolgen kann. Auf diese Weise kann man den Baum auch jederzeit erweitern, ohne dass man etwas umsortieren müsste. Die Suche im Baum erfolgt einfach nach demselben Schema.
Wenn wir unsere Liste von oben durchschütteln ([22, 54, 5, 9, 82, 42, 3, 17, 79, 28, 76, 14, 61, 37, 43]) erhalten wir folgenden Baum:
Je nach Reihenfolge der Elemente in der Ausgangsliste kann der entstehende Baum dann auch anders aussehen. Auch hier gibt es viele unterschiedliche Bäume, die die Nachteile eines Binärbaums (z.B. die mögliche Unwucht in der Verteilung der Elemente) vermeiden, aber in ihren Regeln natürlich komplizierter sind.
Aufgaben
1) Überführe folgende Liste von Zahlen in einen binären Suchbaum: [27, 58, 16, 25, 4, 69, 84, 41, 63, 19]
2) Wie könnte man folgende Liste von Begriffen als binären Suchbaum darstellen? [Krokodil, Elefant, Nashorn, Maus, Marder, Fuchs, Dachs, Panther]
Verzeichnisbaum
Baumstrukturen kann man auch verwenden, um Objekte oder Begriffe in eine bestimmte Ordnung zu bringen. Ein bekanntes Beispiel ist der Verzeichnisbaum, der uns hilft, unsere Dateien im Computer so abzulegen, dass wir sie wieder finden, und dass Zusammgehöriges auch entsprechend abgespeicher wird.
Unter Windows werden Daten in einem Verzeichnisbaum gespeichert. Es können Ordner (Verzeichnis, Directory) angelegt werden. In jedem Ordner können weitere Ordner und Dateien abgelegt werden. Dabei ergibt sich eine Baumstruktur aus Ordnern (Stamm, Äste) und Dateien (Blätter):
- An der Wurzel des Baums steht der "Laufwerk-Buchstabe", z.B. "C:\"
- Für jedes Laufwerk, auch für externe Laufwerke, USB-Stick und CD-Laufwerk, wird ein separater Baum angelegt.
- Die Tiefe der Gliederung kann fast beliebig tief gemacht werden, d.h. Ordner im Ordner im Ordner, etc.
- Programme können ihre Daten an beliebige Stellen speichern und dort wieder ansprechen. Befehle "Speichern unter" und "Öffnen" benutzen und navigieren.
- Zur Navigation im Verzeichnisbaum verwendet man den Windows Explorer.
Die Namen von Ordnern und Dateien können durch "\" getrennt hintereinander geschrieben werden. Dadurch erhält man einen sogenannten Pfad. Beispiel:
C:\Users\Bernd\Documents\Schule\2014-15\Info 6\binaercode.odg
Stammbaum
Eine weitere Anwendung von Baumstrukturen sind z.B. Stammbäume. Ein Stammbaum ist im allgemeinen Sinne die baumförmige Darstellung der Abstammung von Lebewesen, Sachen oder Ideen voneinander, ausgehend von einem oder zwei zugrundeliegenden Exemplaren an der Baumwurzel. Beispiele:
Aufgabe
Erstelle einen Stammbaum deiner Familie.